SuperHack/SuperHack CD.bin/CODING/MISC/ONEWAYFU.ZIP/ONEWAYFU.TXT

Text File | 1996-02-22 | 18.4 KB | 292 lines

     One Way Functions,Insolvable Problems, Static and Dynamic Encryption

A one-way function is a function whose inverse is difficult to compute.  In
finite mathematics, the most difficult problem we have known is to find roots
of algebraic equations, a problem proved insolvable in finite mathematics.  It
may be possible to create functions whose inversions are problems insolvable
in finite mathematics.  Here we shall discuss the possibility and feasibility
to create these functions for data encryption.

     I. INSOLVABLE PROBLEMS, THEORY OF EQUATIONS, AND ONE-WAY FUNCTIONS
A problem in finite mathematics is insolvable if its solution cannot be
obtained through finite number of rational operations, namely, addition,
subtraction, multiplication, and division.  Here, we concern only the existence
of a mathematic method, not how long it takes to compute the solution.  In
finite mathematics, we can always use the exhaustive method to find a solution.
However, the exhaustive method is an ad hoc method and we have to change the
scheme as the problem changes.

If we can derive solution x to a problem defined in a finite field F through
rational operations, then we can apply rational operations to x, namely, to
compute any integer power of x, x^i, and any linear combination of them in
F, i.e., a polynomial of x, a_kx^k+a_(k-1)x^(k-1)+..+a_0, where a_i, i=0 to
k, are in F.  If we want to stay in finite mathematics, then the number of
elements we create must be finite and there must exist a minimum n such that
x^i's, i=1 to n, are linearly dependent, i.e., we can find a_i's in F such that
x^n+(a_(n-1)x^(n-1)+a_(n-2)x^(n-1)+..a_0=0, an algebraic equation of degree n
with x as one of its roots. This equation is irreducible because n is the
minimum.  All these polynomials of x in F form a finite field F', known as
an algebraic extension of F.

We can also extend F to F' with solutions to a set of problems defined in F and
elements of F', rational functions of these solutions in F, are solutions to
some problems in F and must also satisfy some algebraic equations in F.
Elements that cannot satisfy any algebraic equation of a finite degree are
called transcendental, e.g., transcendental numbers and transcendental
functions, which belong to transfinite mathematics.  To solve a problem in
finite mathematics and to find roots of an equation in finite mathematics are,
therefore, related and, if we want to create the hardest problem in finite
mathematics, we have to know theory of equations.

Theory of equations, an analytic theory of permutations and the symmetric
group, is rather complicated.  Briefly, if an equation f(x)=0 defined in F
has n distinct roots x_i, i=1 to n, then f(x)=(x-x_1)(x-x_2)..(x-x_n).
Permutations on the roots will not alter f(x) and they form a group G={A_i,
i=1 to M), where M is the order of G.  The set of all rational functions of
roots of f(x)=0 form a field, an extension F' of F by joining roots to F.  If
we permute x_i's among themselves, then elements in F' are also permuted
among themselves, namely, a mapping g(x) of F' onto F'.  Then roots of
f(g(x))=0 becomes g(x)=x_i.  Inverting g(x)=x_i, we get x=h(x_i) and a root
of an equation may be expressed as rational function of roots of some other
equations.

If roots of every equation were expressed this way, then we could find roots
through a finite number of rational operations on roots of some known or
choice equations.  However, theory of equations asserts that roots of an
equation under G can be expressed as rational functions of roots of other
equations if and only if G has invariant subgroups.  In particular, if roots
of an equation can be expressed as rational functions of roots of choice
equations x^p- A=0's, the group for the equation is called solvable and the
equation, solvable through radicals.  Equations of a degree less than five can
be solved through radicals.  The group for a general equation of degree n is
the symmetric group on n letters, S_n.  Group S_n always has one invariant
subgroup of index 2, the alternating group on n letters, A_n.  Therefore, we
can always decompose an equation into the real part and the imaginary part,
neither of which we can solve when n>4, because A_n is simple and not solvable.
As a result, a general equation of degree n>4 is insolvable in finite
mathematics. To generate S_n or A_n is obviously an attempt to create a problem
insolvable in finite mathematics.

This is the theory.  What happens is that rational operations in finite
mathematics are not unique.  If we have a root of irreducible F(x)=0 under
group G, then we join the root to F to extend it to F', which is isomorphic to
g(x)=h(x) (mod F(x)).  Using rational operations in F' to solve f(x)=0 means to
solve f(x)=0 (mod F(x)).  If solutions to the two equations are different, then
we cannot solve f(x)=0 this way.  If we use rational operations to solve a
problem, we may face the same difficulty.  Therefore, insolvability in finite
mathematics is common to many problems.

We may divide problems into classes, each of which contains problems whose
solutions can be expressed as rational functions of roots of an equation under
a simple group.  According to theory of equations, solutions to classes of
problems are independent because we cannot derive solutions to problems in one
class from solutions to problems in other classes.  The classes of problems
are infinite and the classes of problems we have solved are finite.  Therefore,
insolvability means that we cannot solve new problems based on what we have
known.  Accordingly, if we want to create the hardest problem under a given
condition, then the problem should be a problem combined with as many classes
of problems as possible and the equation associated with each class is of the
highest degree as possible.

The major problem in cryptoanalysis is whether we can find the decipher
function in finite mathematics, namely, through finite number of rational
operations.  A decipher function is a root of some irreducible equation in F,
whose group is G'.  All decipher functions that can be expressed as rational
functions of roots of the equation create G' in some way.  The best
encryption system finite mathematics can offer is a system with G' as large as
possible to assure the degree of the equation is as high as possible, namely,
G'=S_N or A_N, and as many irreducible equations created by the decipher
functions as possible.  To meet this requirement, we should select the set of
decipher functions such that any selection of a few of the decipher functions
from the set can create S_N or A_N.  Therefore, generation of symmetric groups
from some selected elements is essential to create one-way functions and strong
encryption systems.

   II. GENERATION OF SYMMETRIC GROUPS AND UNBREAKABLE ENCRRYPTION SYSTEMS
Generation of the symmetric group through random elements was discussed in
sci.math.research on 05 Jan. 1994.  One possible motive to study this
problem is to create an encryption system insolvable in finite mathematics.
The general belief is, apparently, that we need O(ln(N)) random elements to
generate the symmetric group.  Since ln(2^64) is about 43, it becomes a general
practice to iterate an algorithm 16 to 64 times.  To justify this practice, we
have to assume that elements are distributed evenly.  However, elements of the
symmetric group have no natural order.  The algorithm may order elements such
that all good elements in one place and the bad one, the other place.  As a
result, iterations of the algorithm may be equivalent to selecting elements of
only one kind and may fail to generate the symmetric group.  Besides, there is
no assurance that a few of the decipher functions generated by the algorithm
with any keys will also generate the symmetric group.

The application of generation of the symmetric group also interests my friends
in the Far East and me.  We have some interesting results and more mathematical
details was posted recently on sci.math.research.  Here is the basic result.

THEOREM: It takes no more than three choice elements to generate a finite
group G, which can be either the symmetric group on N letters or its
alternating group.

DEFINITION:  We say a group R contains a set P, if every element of P belongs
to R.  The intersection of all possible R is the minimum group H that contains
P and sometimes we say P generates H.  Group H is unique.  A proper subgroup U
of G is a maximum proper subgroup of G if any subgroup U' containing U must be
either U or G.  There may be many distinct U's. Maximum proper subgroups of G
offers the best way to select elements to create G, because a set P of elements
of G will generate G if there is no maximum proper subgroup of G containing P.

Here, I shall use an example to illustrate how we can create S_5.  The example
is too simple to help anyone to create a strong system and I will not be accused
of exporting encryption technology through the Internet.

To create S_5, we select an element randomly and we probably get an element
involved with only two letters, e.g., (12), because there are 10 of them.  The
possible maximum proper subgroups that contain (12), are [1,2,3,4], [1,2,3,5],
[1,2,4,5],{[123],[45]}, {[124],[35]}, {[125],[34]}, and {(12),[345]}, where
[1,..] denotes the permutation group on the enclosed letters and {a,b..} means
the group generated by the enclosed elements.  Obviously, element (12345) is
not in any of the maximum proper subgroups and {(12),(12345)}=S_5.  If element
(12345) was difficult to find, then we should select element b in one of the
maximum proper subgroups such that b is unique to the subgroup.  Then only one
maximum proper subgroup contains (12) and b.  Selecting element c outside this
maximum proper subgroup, we create S_5 with (12), b, and c.  That is what the
theorem asserts.

We can show that it is feasible and practical to create the best system.
According to the theorem and other studies that the probability that two random
elements to generate S_n or A_n is 1-O(1/n) ( see references posted in
sci.math.research in the thread "generation of permutation groups by random
elements," 05 Jan 1994), there must be a majority of elements having this
property, namely, being highly complex, irregular, and difficult to see how to
construct them from simple operations on a computer, and a small minority of
elements does not have this property, being highly regular, simple, and easy to
construct from simple operations.  However, group multiplication changes
elements around, namely, G={a_i, i=1 to M}=xG={xa_i, i=1 to M}.  In other words,
group G is represented as mappings of a space G of M elements one-to-one onto
itself.

If the representation is irreducible, then the mappings will not leave any
subspace of G unaltered.  In other words, if x is a regular element, then a
small fraction of irregular elements will be changed to regular ones and an
equal number of regular a_i migrating to the majority.  A small fraction of
the majority means a relatively large number for the minority and a choice
selection of a few xa_i's with regular a_i, e.g., four these elements, will
create S_n, because they are irregular.  For simplicity, the cipher function
is the product of these four elements.  Obviously, any four or so of these
cipher functions can also create S_n because they are also irregular.
Therefore, an unbreakable encryption system is a matter of properly combining
some simple operations, not a matter of repeating the same algorithm many
times.

If we have an analytic method of cryptoanalysis, e.g., the method of
differential analysis, then we can also use this method to construct the best
encryption system.  An operation or an algorithm or an element possesses
certain properties to make it easy or difficult to break.  If we quantify
these properties by parameter q, then elements with q near q_0 are the most
difficult to break and become easier when q is farther away from q_0.  The
distribution curve according to q is of a bell shape centered at q_0.
Elements at the two edges of the bell curve are simple and easy to break and
to create.  If we select two elements, one at each edge, we can create some
elements between the two through interpolation.

The bell curve is multi-dimensional and we select elements from various
dimensions, e.g., eight elements from four dimensions.  Using these eight
elements, we can create every element through interpolation.  For elements of a
group, the method of interpolation is a possible group product of the eight
elements.

In either case, we need eight operations.  An operation on 64-bit data can be
implemented with a minimum of two instructions on a 32-bit machine.  Therefore,
the best system with 64-bit blocks needs about twenty instructions on a 32-bit
machine, depending on the efficiency of the instruction set.  Obviously, this
system with a 40-bit key will never be licensed for export, because there is no
way to prevent the user from encrypting data twice with 80-bit key and four
times with a 160-bit key.  The issue of key-length is, apparently, a part of
disinformation to mislead people to believe that the length of keys, not the
algorithm, is the only important factor.

   III. THE DYNAMIC ENCRYPTION SYSTEM AND ITS APPLICATION TO IDENTIFY
             FRIENDS AND FOES, THE GENUINE AND THE COUNTERFEIT
Once we know how to create the symmetric group, we can create the strongest
encryption system to meet whatever we need.  Most encryption systems are static
because they do not depend on time.  We may introduce a new variable, the time
variable, into the system and make the system a dynamic system.  The dynamic
system encrypts the same message into different codes if it is encrypted at
different times.  The one-time pad is an example.  However, the one-time pad is
very difficult to use.  We may use redundancy coding to achieve the the same
feature.

Communication through sound waves is an encryption system.  We encrypt a
message into sound waves and decipher sound waves back to the message at the
receiver.  However, this system has redundancy because sound waves carry not
only the message, but also information about the source that emits them.  This
is why we can identify our relatives through their voices, though we may not
understand the languages they are speaking.  Using this redundancy feature, we
can mathematically simulate a dynamic system.

The new system is consisted of N speakers each speaks a distinct language
with a distinct voice and a timer with a counter to register up to N ticks of
the clock.  When a message comes in for encryption, the system reads the
counter of the timer.  If it is k, then the system uses the k-th speaker to
encrypt the message in the distinct language with the distinct voice the k-th
speaker speaks.  The receiver, detecting the speaker from the voice, will use
the k-th listener to decipher the message.  If the same message is to encrypt
again, the system will use a different speaker and the code will be different
from the previous ones, but the receiver can decipher it without any further
information.  Obviously, the static system uses only one speaker and is
much weaker than the dynamic system.

One of the important applications of data encryption is to keep things secret
and an unbreakable encryption system will do that.  The other is to identify
friends and foes, and the genuine and the counterfeit.  The dynamic system
is very good for the latter, because the time variable may serve as a time
stamp or an official seal.  The conventional method is to use passwords to
identify friends and foes: the guard asks a guest the password and,
answering correctly, the latter is admitted.  However, with modern
eavesdropping and reproduction technologies, one can record the password
and use it to break the system.  If we use the dynamic system, the guard,
speaking in English, asks the guest to answer the password in French.  The
guest, identifying English from the voice of the speaker, using the English
interpreter to decode the message, and issuing the password in French
through the French speaker, is allowed in.  The intruder, using the recorded
password in a different language, will be arrested on the spot.  The
password in a special language is used only once in many years, namely,
once every counter cycle (more than half a million years if N=2^64 and a
1us tick).

For client and server applications, the following exchange is also
unbreakable.  Initiating the exchange, the client asks: "request for
connection; reply in French."  The server replies in French: "connection
completed; reply in Spain."  The phrase "reply in French" and so on serve
as official seals requested by the receivers.  Since an official seal is
used only once every counter cycle, the intruder, having never seen the seal
before, cannot make up a message with the seal by manipulating recorded
messages.  As a result, the receiver is assured that the message received
with the requested seal is genuine.

Finally, one may raise the issue that we may use new operations to solve
problems in finite mathematics, an issue deserving a subject on its own merit.
The fundamental issue is how we find the new operations if they exist.  The
new operations operate on a set p of elements to produce solutions.  The
important way to resolve this issue is the closure of p under the new
operations.  That is, the new operations operate on p and produce some new
ones.  We join these new elements to p and repeat the process until no new
element is generated.  Let the closure of p is P.  If P is finite, then the
new operations, permutations on elements of P, subject to the same rules
governing permutations on elements of P and to find the new operations, if they
exists, may also be a problem insolvable through rational operations in
finite mathematics.  Besides, P cannot contain solutions to all the problems
in finite mathematics, because the set of solutions are unbounded.

If P is infinite, then the new operations are completely defined only in
transfinite mathematics.  We can create these operations.  The redundancy
coding used in the dynamic encryption system is an example.  The
redundancy coding will encrypt a message of n bits into a code of n+k bits.
Dynamic encryption will produce all possible (n+k)-bit codes and n-bit data
belong to (n+k)-bit data through zero extension. Therefore, the closure of
n-bit data under redundancy coding is a set of data of infinite bits.
Therefore, we cannot compromise this system in finite mathematics.  However,
since we use only finite number of cipher functions, we can compromise it
through the exhaustive method.

                      King Lark <[e-mail]>